﻿/*
对于给定的字符集合A,B,C,D,E,F,G,H，依次按给定的出现频率构建哈夫曼树，
并输出字符串ABCDEFGH的哈夫曼序列。哈夫曼树要求左孩子不大于右孩子。
测试用例1：输入：1 2 4 8 16 32 64 128
输出：00000000000001000001000010001001011
测试用例2：输入：5 10 7 9 11 13 14 16
输出：1010011101101010011011100
*/


/*
***改良点***
*1、添加统计输入文本中字符种类数以及每个字符出现的次数的函数
*（这样便可实现对任意输入字符串的编码）
*2、学习如何以文件的格式进行输入
*（这样便可用Huffman树实现文件压缩）
*3、添加解码函数
*/


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


typedef char DataType;
typedef struct HuffmanTreeNode HTNode;
struct HuffmanTreeNode
{
	DataType letter;
	int weight;
	HTNode* left;
	HTNode* right;
	HTNode* parent;
	int flag;//编码时标记是否访问过，0为未访问过
};
typedef struct LinkedListNode LLNode;
typedef struct LinkedListNode //双向链表存放初始节点，用于生成树
{
	HTNode* leaf;
	LLNode* next;
	LLNode* last;
};
typedef struct STACK//遍历时用以生成编码
{//线性栈
	DataType* stackArray;
	int top;
	int bottom;
}Stack;


//树相关函数
HTNode* CreateHuffmanTree(LLNode* Head);
int FindMinAndDel(LLNode* Head);
void HuffmanCoding(HTNode* HTRoot, char target, Stack* stack);
void ReturnToZero(HTNode* HTRoot);
//栈相关函数
Stack* CreateStack(int length);
void Push(Stack* stack, DataType data);
void Pop(Stack* stack);
char BottomElement(Stack* stack);


//Input String："A,B,C,D,E,F,G,H"
int main()
{
	char str[50];
	gets(str);
	int len = strlen(str), flag = 0;
	int times[50] = { 0 };
	//Transfer from char to int
	for (int i = 0, n = 0; i < len; i++) {
		if (str[i] == ' ') {
			flag = 0;
			n++;
			continue;
		}
		else {
			times[n] *= 10;
			times[n] += (str[i] - '0');
		}
	}
	//Intilized nodes
	LLNode* head = (LLNode*)malloc(sizeof(LLNode));//双向链表头结点（不储存值）
	head->next = NULL;
	head->last = NULL;
	LLNode* now = head;//当前操作所在结点
	const int Types = 8;//***字符种类数***
	for (int i = 0; i < Types; i++) {
		LLNode* NewNode = (LLNode*)malloc(sizeof(LLNode));//生成新的链表节点
		now->next = NewNode;//连接到上一个结点上
		NewNode->last = now;
		now = NewNode;//now指针位置移动
		now->leaf = (LLNode*)malloc(sizeof(HTNode));
		now->leaf->letter = 'A' + i;
		now->leaf->weight = times[i];
		now->leaf->left = NULL;
		now->leaf->right = NULL;
		now->leaf->parent = NULL;
		now->leaf->flag = 0;
	}
	now->next = NULL;
	//Create Tree
	HTNode* Root = CreateHuffmanTree(head);
	//HuffmanCode
	const int MAXLENGTH = 10;//***栈容量（10已经足够大了）***
	char input[] = "ABCDEFGH";//***改进点***
	for (int i = 0; i < strlen(input); i++) {
		char letter = input[i];
		Stack* stack = CreateStack(MAXLENGTH);//在此处创建栈，否则每次循环要置空栈
		HuffmanCoding(Root, letter, stack);
		ReturnToZero(Root);//把树每个结点的flag变回0
	}
	free(head);
	return 0;
}


//Tree
/**1
*@brief：生成Huffman树并返回其根节点
*@param：head 链表的头指针
*/
HTNode* CreateHuffmanTree(LLNode* head) {
	while(head->next->next)//当多于一个结点时
	{
		LLNode* NewNode = (LLNode*)malloc(sizeof(LLNode));//生成新的链表节点
		NewNode->leaf = (HTNode*)malloc(sizeof(HTNode));//初始化一个树新结点
		NewNode->leaf->letter = 0;
		NewNode->leaf->weight = 0;
		NewNode->leaf->left = NULL;
		NewNode->leaf->right = NULL;
		NewNode->leaf->parent = NULL;
		NewNode->leaf->flag = 0;
		LLNode* FirstMin = FindMinAndDel(head);//当前链表中所含树节点权重最小的结点
		LLNode* SecondMin = FindMinAndDel(head);//当前链表中所含树节点权重第二小的结点
		NewNode->leaf->left = FirstMin->leaf;
		NewNode->leaf->right = SecondMin->leaf;
		NewNode->leaf->weight = FirstMin->leaf->weight + SecondMin->leaf->weight;
		FirstMin->leaf->parent = NewNode->leaf;//父指针指回
		SecondMin->leaf->parent = NewNode->leaf;
		//新结点加入链表
		if(head->next){
			NewNode->next = head->next;
			NewNode->last = head;
			head->next->last = NewNode;
			head->next = NewNode;
		}
		else {//放入最后一个结点
			NewNode->next = NULL;
			NewNode->last = head;
			head->next = NewNode;
		}
		CreateHuffmanTree(head);
	}
	return (head->next->leaf);//最后剩下的一个结点中包含的树结点即是Huffman树的根节点
}
/**2
*@brief：找到当前链表中所含树节点权重最小的结点，并从链表中删去它
*@param：head 链表的头指针
*/
int FindMinAndDel(LLNode* Head) {
	LLNode* MinNode = Head->next;//从第一个存值节点开始查找
	LLNode* now = MinNode;
	//寻找
	while (now)//链表当前不为空时，进行比较
	{
		if (MinNode->leaf->weight > now->leaf->weight) {
			MinNode = now;
		}
		else
			now = now->next;
	}
	//删除
	if (MinNode->next) {//MinNode不是最后一个结点时
		MinNode->last->next = MinNode->next;
		MinNode->next->last = MinNode->last;
	}
	else
		MinNode->last->next = NULL;
	return MinNode;
}
/**3
*@brief：生成输入的单个字符的Huffman编码并打印出来（不换行）
*@param：HTRoot 建好的Huffman树的根节点；target 要编码的字符；stack 用来保存编码的栈
*/
void HuffmanCoding(HTNode* HTRoot, char target, Stack* stack) {
	HTNode* root = (HTNode*)malloc(sizeof(HTNode));
	root = HTRoot;
	root->flag = 1;
	if (root->left == NULL && root->right == NULL) {
		if (root->letter == target) {
			while (stack->top - stack->bottom > 0)
				printf("%c", BottomElement(stack));
			//栈不为空即打印栈底元素，直到栈为空
		}
		else {
			root = root->parent;
			Pop(stack);
			HuffmanCoding(root, target, stack);
		}
	}
	else if (root->left != NULL && root->left->flag == 0) {
		Push(stack, '0');
		root = root->left;
		HuffmanCoding(root, target, stack);
	}
	else if (root->right != NULL && root->right->flag == 0) {
		Push(stack, '1');
		root = root->right;
		HuffmanCoding(root, target, stack);
	}
	else {
		root = root->parent;
		Pop(stack);
		HuffmanCoding(root, target, stack);
	}
}
/**4
*@brief：将进行过编码的Huffman树的所有结点的flag重置为0
*@param：root 经过一次编码的Huffman树的根节点
*/
void ReturnToZero(HTNode* HTRoot) {//和前序遍历方法相同
	if (HTRoot != NULL) {
		HTRoot->flag = 0;
		ReturnToZero(HTRoot->left);
		ReturnToZero(HTRoot->right);
	}
}

//Stack
/**1
*@brief：创建一个空栈
*@param：length 栈的最大容量
*/
Stack* CreateStack(int length)
{
	Stack* stack = (Stack*)malloc(sizeof(Stack));
	if (stack) {
		//分配栈空间
		stack->stackArray = (DataType*)malloc(length * sizeof(DataType));
		//置为空栈
		stack->bottom = 0;//0不放元素，栈底元素在1处
		stack->top = 0;
		stack->stackArray[stack->top] = NULL;
	}
	return stack;
}
/**2
*@brief：栈外元素从栈顶入栈
*/
void Push(Stack* stack, DataType data)
{
	stack->top++;
	stack->stackArray[stack->top] = data;
}
/**3
*@brief：栈内元素从栈顶出栈
*/
void Pop(Stack* stack)
{
	if (stack->top > stack->bottom) {
		//如果栈不空，则出栈
		stack->top -= 1;
	}
	else {
		//栈已经空了，出栈失败
		return;
	}
}
/**4
*@brief：返回栈底元素
*/
char BottomElement(Stack* stack)
{
	if (stack->top > stack->bottom) {
		//如果栈不空，返回栈底元素
		stack->bottom += 1;
		return stack->stackArray[stack->bottom];
	}
	else {
		//栈已经空了，出栈失败
		return 0;
	}
}